1. Technical Field
The invention relates generally to statistical timing of a circuit, and more particularly, to a method, system, and program product for accommodating spatially-correlated variation in one or more process parameters during statistical timing of a circuit.
2. Background Art
As the sizes of transistors and interconnects in integrated circuits have decreased, variabilities in process parameters have led to corresponding increases in the difficulty of modeling and predicting circuit performance. Variations in process parameters can be inter-die variations (i.e., variations from die to die) or intra-die variations (i.e., variations within a single chip). Inter-die variations affect all components on a single chip similarly, while intra-die variations affect similar components on a single chip differently.
Statistical static timing analysis (SSTA) has become a widely-recognized technique for predicting statistical timing characteristics of digital circuits. Various approaches to SSTA are known, and include path-based, block-based, bounding, parameterized, and Monte-Carlo methods. A particularly promising technique is parameterized block-based SSTA, which models variation in gate delays, arrival times, and required times as a linear function of Gaussian independent sources of variation in process parameters. As such, parameterized block-based SSTA accommodates both independent and globally-correlated variations with speed and accuracy. The technique has also been used with non-Gaussian distributions.
However, the approaches to parameterized block-based SSTA to date are not problem-free. For example, the quad tree approach of Agarwal et al., ACM/IEEE Asia-Pacific Design Automation Conference (ASP-DAC), January 2003, pp. 271–276, assumes that a gate delay is represented as a linear combination of independent variables corresponding to cells of hierarchical rectangular grids, wherein the overlap of the grids models spatial correlation of the gate delays. This approach assumes that the coefficients of this linear combination are known. It is not clear, however, how these coefficients are computed in modeling a given spatial variation.
The approach of Chang et al., Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, 2003, pp. 621–625, is also unsatisfactory. Using a rectangular grid superimposed onto a circuit, this approach assumes that a correlation matrix is known for gates situated in different grid cells. Principal component analysis (PCA) is then used to represent gate delays as linear functions of uncorrelated parameters. However, such an approach presents computational difficulties. For example, in a 10 mm by 10 mm chip having an effective correlation distance of 100 microns, a grid according to the approach of Chang et al. requires an eigenvalue decomposition (EVD) or singular value decomposition (SVD) of a 10,000 by 10,000 covariance matrix. Such decomposition is computationally expensive.
In addition, in the example above, gates separated by 200 microns or more are not correlated. As a result, modeling variation in such a chip requires at least 2500 (i.e., 50 by 50) independent random variables. Due to the number of uncorrelated variables, PCA cannot reduce the number of independent variables to fewer than 2500. Thus, using the PCA approach of Chang et al., large chips having relatively small correlation distances require a very large matrix and the computation of a prohibitively large number of eigenvalues and eigenvectors.
Other known approaches, whereby correlation coefficients are computed directly from a correlation matrix, are similarly unsatisfactory. First, such approaches require multiplication of the correlation matrix and canonical forms. This is both computationally expensive and adversely affects the efficiency of parameterized block-based SSTA. Second, the use of linear forms of delays, arrival times, and required times with correlated terms complicates other necessary operations, such as the computation of standard deviations, controlling and pruning small terms, reporting results, etc.
Accordingly, a need exists for a method for accommodating spatially-correlated variation in one or more process parameters during statistical timing of a circuit that does not suffer the deficiencies of the approaches described above.